package mylib.dir;

import java.util.Comparator;

/**
 * Created with IntelliJ IDEA.
 * User: 1
 * Date: 16.07.12
 * Time: 20:05
 * To change this template use File | Settings | File Templates.
 */
public class SimpleUtils {
    public static double toDegrees(double radians) {
        return radians / (Math.PI * 2) * 360.0;

    }

    public static double toRadians(double degrees) {
        return degrees / 360. * Math.PI * 2;
    }

    public static Integer[] getOrder(int len) {
        Integer[] a = new Integer[len];
        for (int i = 0; i < len; ++i)
            a[i] = i;
        return a;
    }

    public static <K> boolean nextPermutation(K[] array, Comparator<K> comparator) {
        int i = -1;
        for (i = array.length - 2; i >= 0; --i)
            if (comparator.compare(array[i], array[i + 1]) < 0)
                break;
        if (i == -1)
            return false;
        int j = -1;
        for (j = array.length - 1; j > i; --j)
            if (comparator.compare(array[j], array[i]) > 0)
                break;
        K tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
        for (int l = i + 1, r = array.length - 1; l < r; ++l, --r) {
            tmp = array[l];
            array[l] = array[r];
            array[r] = tmp;
        }
        return true;
    }

    public static <K extends Comparable<K>> boolean nextPermutation(K[] array) {
        return nextPermutation(array, new Comparator<K>() {
            @Override
            public int compare(K o1, K o2) {
                return o1.compareTo(o2);
            }
        });
    }

    public final static int fftMod = 1007681537;
    private final static int root = 665;
    private final static int root_1 = 184867891;
    private final static int root_pw = 1 << 20;

    public static void fft(int[] a, boolean invert) {
        if (Integer.bitCount(a.length) != 1)
            throw new IllegalArgumentException("length of array must be power of two");
        if (a.length > root_pw)
            throw new IllegalArgumentException("this length of array is not supported");
        int n = a.length;

        for (int i = 1, j = 0; i < n; ++i) {
            int bit = n >> 1;
            for (; j >= bit; bit >>= 1)
                j -= bit;
            j += bit;
            if (i < j) {
                int c = a[i];
                a[i] = a[j];
                a[j] = c;
            }
        }

        for (int len = 2; len <= n; len <<= 1) {
            int wlen = invert ? root_1 : root;
            for (int i = len; i < root_pw; i <<= 1)
                wlen = (int) ((long) wlen * wlen % fftMod);
            for (int i = 0; i < n; i += len) {
                int w = 1;
                for (int j = 0; j < len / 2; ++j) {
                    int u = a[i + j], v = (int) ((long) a[i + j + len / 2] * w % fftMod);
                    a[i + j] = u + v < fftMod ? u + v : u + v - fftMod;
                    a[i + j + len / 2] = u - v >= 0 ? u - v : u - v + fftMod;
                    w = (int) ((long) w * wlen % fftMod);
                }
            }
        }
        if (invert) {
            int nrev = MathUtils.inverse(n, fftMod);
            for (int i = 0; i < n; ++i)
                a[i] = (int) ((long) a[i] * nrev % fftMod);
        }
    }

}
